//给定一个整数数组 nums ，返回 nums[i] XOR nums[j] 的最大运算结果，其中 0 ≤ i ≤ j < n 。 
//
// 
//
// 
// 
// 示例 1： 
// 
// 
//
// 
//输入：nums = [3,10,5,25,2,8]
//输出：28
//解释：最大运算结果是 5 XOR 25 = 28. 
//
// 示例 2： 
//
// 
//输入：nums = [0]
//输出：0
// 
//
// 示例 3： 
//
// 
//输入：nums = [2,4]
//输出：6
// 
//
// 示例 4： 
//
// 
//输入：nums = [8,10,2]
//输出：10
// 
//
// 示例 5： 
//
// 
//输入：nums = [14,70,53,83,49,91,36,80,92,51,66,70]
//输出：127
// 
//
// 
//
// 提示： 
//
// 
// 1 <= nums.length <= 2 * 10⁵ 
// 0 <= nums[i] <= 2³¹ - 1 
// 
//
// 
//
// 进阶：你可以在 O(n) 的时间解决这个问题吗？ 
//
// 
//
// 
// 注意：本题与主站 421 题相同： https://leetcode-cn.com/problems/maximum-xor-of-two-
//numbers-in-an-array/ 
//
// Related Topics 位运算 字典树 数组 哈希表 👍 86 👎 0


package LeetCode.editor.cn;


/**
 * @author ldltd
 * @date 2025-02-27 09:52:36
 * @description LCR 067.数组中两个数的最大异或值
 
 */
 
public class Ms70jA {
    public static void main(String[] args) {
    //测试代码
    Ms70jA fun = new Ms70jA();
    Solution solution= fun.new Solution();
        System.out.println(solution.findMaximumXOR(new int[]{3, 10, 5, 25, 2, 8}));
    }

//leetcode submit region begin(Prohibit modification and deletion)
class Solution {
        //Onlogn  构造字典树，然后对每个数贪心最大
    public int findMaximumXOR(int[] nums) {
        Trie p=new Trie();
        for (int i = 0; i < nums.length; i++) {
            p.insert(nums[i]);
        }
        int res=0;
        for (int num : nums) {
            res=Math.max(res,p.xor(num));
        }
        return res;
    }
    class Trie{
        Trie [] ne;
        Trie(){
            ne=new Trie[2];
        }
        void insert( int num){
            Trie p=this;
            for (int i = 31; i >= 0; i--) {
                int bit = (num >> i) & 1;
                if (p.ne[bit] == null) {
                    p.ne[bit] = new Trie();
                }
                p = p.ne[bit];
            }
        }
        int xor(int num){
            Trie p=this;
            int t=0;
            //每一对结果会被匹配两次，长的那个匹配短的会提前返回，但是短的匹配长的可以正确计算
            for (int i = 31; i >= 0; i--) { // 从高位到低位
                int bit = (num >> i) & 1;
                if (p.ne[1 - bit] != null) { // 尽量选择相反的位，最大化 XOR
                    t |= (1 << i);
                    p = p.ne[1 - bit];
                } else {
                    p = p.ne[bit];
                }
            }
            return t;
        }
    }

        // 字典树的根节点
        Trie1 root = new Trie1();
        // 最高位的二进制位编号为 30
        static final int HIGH_BIT = 30;

        public int findMaximumXOR1(int[] nums) {
            int n = nums.length;
            int x = 0;
            for (int i = 1; i < n; ++i) {
                // 将 nums[i-1] 放入字典树，此时 nums[0 .. i-1] 都在字典树中
                add(nums[i - 1]);
                // 将 nums[i] 看作 ai，找出最大的 x 更新答案
                x = Math.max(x, check(nums[i]));
            }
            return x;
        }

        public void add(int num) {
            Trie1 cur = root;
            for (int k = HIGH_BIT; k >= 0; --k) {
                int bit = (num >> k) & 1;
                if (bit == 0) {
                    if (cur.left == null) {
                        cur.left = new Trie1();
                    }
                    cur = cur.left;
                }
                else {
                    if (cur.right == null) {
                        cur.right = new Trie1();
                    }
                    cur = cur.right;
                }
            }
        }

        public int check(int num) {
            Trie1 cur = root;
            int x = 0;
            for (int k = HIGH_BIT; k >= 0; --k) {
                int bit = (num >> k) & 1;
                if (bit == 0) {
                    // a_i 的第 k 个二进制位为 0，应当往表示 1 的子节点 right 走
                    if (cur.right != null) {
                        cur = cur.right;
                        x = x * 2 + 1;
                    } else {
                        cur = cur.left;
                        x = x * 2;
                    }
                } else {
                    // a_i 的第 k 个二进制位为 1，应当往表示 0 的子节点 left 走
                    if (cur.left != null) {
                        cur = cur.left;
                        x = x * 2 + 1;
                    } else {
                        cur = cur.right;
                        x = x * 2;
                    }
                }
            }
            return x;
        }

    class Trie1 {
        // 左子树指向表示 0 的子节点
        Trie1 left = null;
        // 右子树指向表示 1 的子节点
        Trie1 right = null;
    }

}

//leetcode submit region end(Prohibit modification and deletion)

}
